import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-21
 * Time: 8:57
 */
public class Test {
    public int countCharacters(String[] words, String chars) {
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0; i < chars.length(); i++) {
            char ch = chars.charAt(i);
            if(map.get(ch) == null) {
                map.put(ch,1);
            }else {
                map.put(ch,map.get(ch) + 1);
            }
        }

        int ret = 0;
        for(String str : words) {
            for(int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if(map.get(ch) == null || map.get(ch) == 0) {
                    break;
                }else {
                    map.put(ch,map.get(ch) - 1);
                }
            }
            ret += str.length();
        }
        return ret;
    }

    public boolean isSubsequence1 (String S, String T) {
        // write code here
        if(S == null || T == null) return false;
        int lenStr = S.length();
        int lenSub = T.length();
        if(lenStr == 0 || lenSub == 0) return false;

        int[] nextValue= new int[lenSub];
        getNext(T,nextValue);
        int i = 0;
        int j = 0;
        while(i < lenStr && j < lenSub) {
            if(j == -1 || S.charAt(i) == T.charAt(j)) {
                i++;
                j++;
            }else {
                j = nextValue[j];
            }
        }
        if(j >= lenSub) {
            return true;
        }

        return false;

    }

    private static void getNext(String sub, int[] nextValue) {
        nextValue[0] = -1;
        nextValue[1] = 0;
        int k = 0;
        int i = 2;
        while(i < sub.length()){
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)) {
                if(sub.charAt(i-1) == sub.charAt(nextValue[i-1])) {
                    nextValue[i] = nextValue[nextValue[i-1]];
                }else {
                    nextValue[i] = k + 1;
                }
                i++;
                k++;
            }else {
                k = nextValue[k];
            }
        }
    }

    public boolean isSubsequence (String S, String T) {
        // write code here
        int i = 0;
        int j = 0;
        while(i < S.length() && j < T.length()) {
            if(S.charAt(i) == T.charAt(j)) {
                i++;
                j++;
            }else {
                i++;
            }
        }
        if(j < T.length()) {
            return false;
        }

        return true;
    }
}
